题解 CF156B@洛谷 | 156B@Codeforces 【Suspects】

$n$ 个人中有 $1$ 个罪犯，每个人说一句话，说第 $i$ 个人是/不是罪犯，其中有 $m$ 句真话，要判断这些话的真假。

思路：

首先假设所有人都不是罪犯，统计出真话条数，然后枚举每一个人，在这个真话条数的基础上加上这个人是罪犯时对答案的贡献，如果刚好有 $m$ 句真话，标记有嫌疑，最后判断即可。

但是这个贡献怎么求呢？

很简单，如果所有人都不是罪犯，则真话条数就是 $a_i\lt 0$ 的数量；当 $x$ 是罪犯时，减去 $a_i=-x$ 的数量，加上 $a_i=x$ 的数量，即为最新的贡献，这里在读入时也处理出来。

最后话的真假的判断方式也很简单：

如果 $i$ 指控一个人是罪犯：经过如上处理，发现他不可能是罪犯，则为假话；如果他可能是罪犯且嫌疑人数为 $1$，则为真话；否则不确定。说一个人不是罪犯的情况类似，不展开细说，可以参考代码。

代码：

//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
#define loop while(true)
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define per(x,y,z) for(int x=y;x>=z;x--)
#define fil(x,y) memset(x, y, sizeof(x))
#define mulT0 int T; for(scanf("%d", &T);T;T--)
#define mulT1 int T, rnds; for(scanf("%d", &T),rnds=1;rnds<=T;rnds++)
using namespace std;
typedef long long ll;
const int N = 1e5+5;

int n, m, a[N], contribution[N], suspect[N], tot, s;

int main() {
	scanf("%d%d", &n, &m);
	rep(i, 1, n) {
		scanf("%d", &a[i]);
		if(a[i] > 0) ++contribution[a[i]];
		else --contribution[-a[i]], ++s;
	}
	rep(i, 1, n) if(s + contribution[i] == m) suspect[i] = 1, ++tot;
	rep(i, 1, n) {
		if(a[i] > 0) {
			if(!suspect[a[i]]) puts("Lie");
			else if(tot == 1) puts("Truth");
			else puts("Not defined");
		}
		else {
			if(!suspect[-a[i]]) puts("Truth");
			else if(tot == 1) puts("Lie");
			else puts("Not defined");
		}
	}
	return 0;
}